public class Solution1201 {
    public int nthUglyNumber(int n, int a, int b, int c) {
        long d=lcm(a,b),e=lcm(a,c),f=lcm(b,c),g=lcm(lcm(a,b),c);
        long l=1,r=2000000000,ans=-1;
        while (l<=r){
            long mid=l+(r-l)/2;
            long count=mid/a+mid/b+mid/c-mid/d-mid/e-mid/f+mid/g;
            if (count>=n){
                ans=mid;
                r=mid-1;
            }else {
                l=mid+1;
            }
        }
        return (int)ans;
    }

    private long lcm(long a, long b) {
        return a*b/gcd(a,b);
    }

    private long gcd(long a, long b) {
        if (a<b){
            long t=a;
            a=b;
            b=t;
        }
        return a%b==0?b:gcd(b,a%b);
    }

    public static void main(String[] args) {
        System.out.println(new Solution1201().nthUglyNumber(5,2,11,13));
    }
}
